#include <stdio.h>

// 最大子序列和问题， 如果最大和为负数， 则返回0

int maxSubSequence1(int arr[], int size) {
    if (size <= 0) {
        return 0;
    }

    int i, j, k;
    int currSum = 0, maxSum = 0;

    for (i = 0; i < size; i++) { // 起点
        for (j = i; j < size; j++) { // 终点
            currSum = 0;
            for (k = i; k <= j; k++) { // 求出给定区间i, j的和
                currSum += arr[k];
            }

            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
    }

    return maxSum;
}

int maxSubSequence2(int arr[], int size) {
    if (size <= 0) {
        return 0;
    }

    int i, j, k;
    int currSum = 0, maxSum = 0;

    for (i = 0; i < size; i++) { // 起点
        currSum = 0; // 起点更新时， 重置currSum
        for (j = i; j < size; j++) { // 终点
            currSum += arr[j]; // 终点改变， 在前一次的基础上加

            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
    }

    return maxSum;
}

static int divide(int arr[], int left, int right) {
    if (left == right) { // 只有一个元素时
        return arr[left] > 0 ? arr[left] : 0;
    }

    int mid = (left + right) >> 1;
    int lMaxSum = divide(arr, 0, mid); // 左边部分最大和
    int rMaxSum = divide(arr, mid + 1, right); // 右边部分最大和

    // 中间部分求解
    int currSum = 0, lTmpMax = arr[mid], rTmpMax = arr[mid + 1];
    int i;
    for (i = mid; i >= left; i--) {
        currSum += arr[i];
        if (currSum > lTmpMax) {
            lTmpMax = currSum;
        }
    }

    currSum = 0;
    for (i = mid + 1; i <= right; i++) {
        currSum += arr[i];
        if (currSum > rTmpMax) {
            rTmpMax = currSum;
        }
    }

    // 第三种情况的答案
    int maxSum = lTmpMax + rTmpMax;

    // 三个和 求最大
    if (lMaxSum > maxSum) {
        maxSum = lMaxSum;
    }
    if (rMaxSum > maxSum) {
        maxSum = rMaxSum;
    }

    return maxSum;
}

int maxSubSequence3(int arr[], int size) {
    if (size <= 0) {
        return 0;
    }
    return divide(arr, 0, size - 1);
}

int maxSubSequence4(int arr[], int size) {
    if (size <= 0) {
        return 0;
    }
    int i = 0, currSum = 0, maxSum = 0;
    for (; i < size; i++) {
        currSum += arr[i];

        // 如果当前和大于maxSum, 则更新maxSum
        if (currSum > maxSum) {
            maxSum = currSum;
        }

        // 如果currSum<0， 则重置currSum， 即抛弃currSum对应的那些元素
        else if (currSum < 0) {
            currSum = 0;
        }
    }

    return maxSum;
}

int main(int argc, char const *argv[])
{
    int arr[] = {1, 2, 3, 4, -4, 5, -5, 6, -20};
    int size = sizeof(arr) / sizeof(int);

    printf("%d\n", maxSubSequence1(arr, size));
    printf("%d\n", maxSubSequence2(arr, size));
    printf("%d\n", maxSubSequence3(arr, size));
    printf("%d\n", maxSubSequence4(arr, size));
    return 0;
}
